/**
 * 
 */
package leetCode;

import java.util.Arrays;

/**
 * @author zhong
 *
 */
public class LargestPerimeterTriangle {
	public int largestPerimeter(int[] A) {
		Arrays.sort(A);
		int maxRec = 0;
		for (int i = 0; i < A.length; i++) {
			int a = A[i];
			for (int j2 = i + 1; j2 < A.length; j2++) {
				int b = A[j2];
				int c_1 = a + b;
				if (maxRec > c_1 * 2)
					continue;
				int idx = Arrays.binarySearch(A, c_1);
				if (idx < 0) {
					idx = -idx - 1;
				}
				idx -= 1;
				if (idx > j2) {
					int sum = a + b + A[idx];
					if (sum > maxRec)
						maxRec = sum;
				}
			}
		}
		return maxRec;
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int[] A = { 3, 2, 3, 6 };
		System.out.println(new LargestPerimeterTriangle().largestPerimeter(A));
	}

}
